package com.leetcode.algorithm.y22.m07.w4;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1249. 移除无效的括号
 * 
 * https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses/
 * 
 * @author jie.deng
 *
 */
class Question1249Solution01 {

	public String minRemoveToMakeValid(String s) {
		StringBuilder builder = new StringBuilder();
		// stack里存放的是'('在builder中的索引
		Deque<Integer> stack = new ArrayDeque<>();
		int len = s.length();
		int idx = 0;
		int delCnt = 0;
		while (idx < len) {
			char ch = s.charAt(idx);
			if (ch == ')') {
				if (stack.isEmpty()) {
					// 无效的')'不加入到builder
					delCnt++;
				} else {
					stack.pop();
					builder.append(ch);
				}
			} else if (ch == '(') {
				stack.push(idx - delCnt);
				builder.append(ch);
			} else {
				builder.append(ch);
			}
			idx++;
		}
		while (!stack.isEmpty()) {
			// 删除无效的'('
			int i = stack.pop().intValue();
			builder.deleteCharAt(i);
		}
		return builder.toString();
	}

}